# 遍历整个列表，然后把一个最小值放到一个新的列表 或 列表的头部中

def select_sort(li: list) -> list:
    """
    选择排序？
    :param li:
    :return:
    """
    new_li = []  # 空间利用率也低
    for i in range(len(li)):
        min_val = min(li)  # python 原生的获取最值方法不要在算法题中用，O(n)
        new_li.append(min_val)
        li.remove(min_val) # 列表删除元素的复杂度是O(n)
    return new_li


def select_sort_v2(li: list) -> list:
    """
    选择排序, O(n2)
    :param li:
    :return:
    """
    for i in range(len(li) - 1):  # 找第几轮的最小值
        min_i = i
        for j in range(i, len(li)):
            if li[j] < li[min_i]:
                min_i = j

        li[i], li[min_i] = li[min_i], li[i]
    return li

